#include <bits/stdc++.h>
// 2025/01/30
// tag: math
// Author: Zhang Muen
using namespace std;

bool is_prime[2000066];
int cnt, primes[2000066];

void init_sieve()
{
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < 2000066; ++i) 
        is_prime[i] = true;
    for (int i = 2; i < 2000066; ++i) {
        if (is_prime[i]) {
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j) {
            int64_t prime = primes[j];
            if (i * prime > 2000066)
                break;
            is_prime[i * prime] = false;
            if (i % prime == 0)
                break;
        }
    }
    }

int64_t euler_sieve(int64_t n){
    return *upper_bound(primes, primes + cnt, n - 1);
}

template <typename T>
vector<T> RandomArrangement(const vector<T>& nums)
{
    // 使用当前时间和随机数生成器的种子来初始化随机数生成器
    srand(rand() + time(nullptr));
    int64_t n = nums.size();
    // 使用欧拉筛法生成一个小于等于n的最大素数
    int64_t p = euler_sieve(n);
    // 生成一个随机数t，确保t不是p的倍数
    int64_t t = 0;
    while (t % p == 0)
        t = euler_sieve(rand() % 1000033);
    vector<pair<int64_t, int64_t>> pos(n);
    for (int64_t i = 0; i < n; i++)
        pos[i] = { (i + 1) * t % p, i };
    sort(pos.begin(), pos.end());
    vector<T> res(n);
    for (int64_t i = 0; i < n; i++)
        res[i] = nums[pos[i].second];
    return res;
}

void isRandom(int trials, int vectorSize)
{
    // 创建一个大小为vectorSize的vector，每个元素是一个unordered_map，用于记录每个位置上每个数字出现的次数
    vector<unordered_map<int, int>> positionCounts(vectorSize);

    // 创建一个大小为vectorSize的vector，每个元素的值为其索引，即原始顺序
    vector<int> original(vectorSize);
    for (int i = 0; i < vectorSize; ++i) {
        original[i] = i;
    }

    for (int i = 0; i < trials / 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            vector<int> temp = RandomArrangement(original);
            // 统计每个位置上每个数字出现的次数
            for (int pos = 0; pos < vectorSize; ++pos) {
                positionCounts[pos][temp[pos]]++;
            }
        }
        // 输出当前试验的进度
        cout << "Progress: " << i + 1 << "/" << trials / 100 << endl;
    }

    int pos = 0;
    double s = 0;
    for (unordered_map<int, int>& counts : positionCounts) {
        double AverageValue = trials / static_cast<double>(vectorSize);
        double SquareDifference = 0;
        for (const auto& count : counts) {
            SquareDifference += pow(count.second - AverageValue, 2);
        }
        // 计算每个位置上每个数字出现次数的标准差
        double StandardDeviation = sqrt(SquareDifference / vectorSize);
        cout << "Position: " << ++pos << ", Standard Deviation: " << StandardDeviation << endl;
        s += StandardDeviation;
    }
    cout << "Sum: " << s << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    auto start = chrono::high_resolution_clock::now();
    init_sieve();
    isRandom(10000, 1000);
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
    cout << "Time taken: " << duration.count() << " milliseconds" << endl;
    return 0;
}
// now 321472ms